#ifndef LEETCODE_CN_CPP_PROBLEMS_1_H
#define LEETCODE_CN_CPP_PROBLEMS_1_H

#include <unordered_map>
#include <vector>
using namespace std;

namespace problem_1
{

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_multimap<int, int> valIndex;
        for (int i = 0; i < nums.size(); ++i)
        {
            valIndex.emplace(nums[i], i);
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            int a = nums[i];
            int b = target - a;
            auto range = valIndex.equal_range(b);
            if (range.first == valIndex.end())
            {
                continue;
            }
            for (auto it = range.first; it != range.second; it++)
            {
                if (it->second != i)
                {
                    return {min(i, it->second), max(i, it->second)};
                }
            }
        }
        return {};
    }
};

} // namespace problem_1

#endif //LEETCODE_CN_CPP_PROBLEMS_1_H